Duff's device

In computer science, Duff's device is an optimized implementation of a serial copy that uses a technique widely applied in assembly language for loop unwinding. Its discovery is credited to Tom Duff in November of 1983, who at the time was working for Lucasfilm. It is perhaps the most dramatic use of case label fall-through in the C programming language to date. Duff does not claim credit for discovering the concept of loop unrolling, just this particular expression of it in C.

Contents

Background

Loop-unrolling revolves around lowering the number of branches made, by batching them together. To handle cases where the number of iterations is not divisible by the unrolled-loop increments, a common technique is to jump directly into the middle of the unrolled loop for copying the remainder.

Duff was looking for a similar optimization for his case, and succeeded in doing so in C, unrolling a loop into a loop which assigns (up to) 8 values on each iteration.

Original version

Traditionally, a serial copy would look like:

do {                          /* count > 0 assumed */
    *to = *from++;            /* Note that the 'to' pointer is NOT incremented */
} while(--count > 0);

Note that to is not incremented because Duff was copying to a single memory-mapped output register.

While optimizing this, Duff realized that an unrolled version of his loop could be implemented by interlacing the structures of a switch and a loop.

send(to, from, count)
register short *to, *from;
register count;
{
	register n = (count + 7) / 8;
	switch(count % 8) {
	case 0:	do {	*to = *from++;
	case 7:		*to = *from++;
	case 6:		*to = *from++;
	case 5:		*to = *from++;
	case 4:		*to = *from++;
	case 3:		*to = *from++;
	case 2:		*to = *from++;
	case 1:		*to = *from++;
		} while(--n > 0);
	}
}

Notice that device can just as easily be applied with any other size for the unrolled loop, not just 8.

Reason it works

Based on an algorithm used widely by programmers coding in assembly for minimizing the number of tests and branches during a copy, Duff's device appears out of place when implemented in C. The device is valid, legal C by virtue of two attributes in C:

  1. Relaxed specification of the switch statement in the language's definition. At the time of the device's invention this was the first edition of The C Programming Language which requires only that the controlled statement of the switch be a syntactically valid (compound) statement within which case labels can appear prefixing any sub-statement. In conjunction with the fact that, in the absence of a break statement, the flow of control will fall-through from a statement controlled by one case label to that controlled by the next, this means that the code specifies a succession of count copies from sequential source addresses to the memory-mapped output port.
  2. The ability to legally jump into the middle of a loop in C.

Note that, as documented in the comment appearing in Duff's un-optimized version, the code assumes that count is strictly positive.

Performance

Many compilers will optimize the switch into a jump table just as would be done in an assembler implementation. C's default fall-through in case statements has long been one of its most controversial features; Duff observed that "This code forms some sort of argument in that debate, but I'm not sure whether it's for or against."[1]

The primary increase in speed versus a simple, straightforward loop comes from loop unwinding, which reduces the number of branches performed (which are computationally expensive due to the need to flush - and hence stall - the pipeline). The switch/case statement is used to handle the remainder of the data not evenly divisible by the number of operations unrolled (in this example, 8 byte moves are unrolled, so the switch/case handles an extra 1–7 bytes automatically).

This automatic handling of the remainder may not be the best solution on all systems and compilers — in some cases two loops may actually be faster (one loop, unrolled, to do the main copy, and a second loop to handle the remainder). The problem appears to come down to the ability of the compiler to correctly optimize the device; it may also interfere with pipelining and branch prediction on some architectures.[2] When numerous instances of Duff's device were removed from the XFree86 Server in version 4.0, there was an improvement in performance.[3] Therefore, when considering using this code, it may be worth running a few benchmarks to verify that it actually is the fastest code on the target architecture, at the target optimization level, with the target compiler.

Stroustrup's version

The original Device was made for copying to a (memory-mapped) register. To actually copy memory from one location to another, an auto-increment must be added to every reference to to, like so:

 *to++ = *from++;

This modified form of the Device appears as a "what does this code do?" exercise in Bjarne Stroustrup's book The C++ Programming Language, presumably because novice programmers cannot be expected to know about memory-mapped output registers. However, the standard C library provides the function memcpy for this purpose; it will not perform worse than this code, and may contain architecture specific optimizations that will make it significantly faster.

Books

References

This article was originally based on material from the Free On-line Dictionary of Computing, which is licensed under the GFDL.

  1. ^ Duff's device from FOLDOC
  2. ^ James Ralston's USENIX 2003 Journal
  3. ^ Ted Tso on XFree86 and performance, Linux Kernel Archive ML

External links